package com.gitee.wsl.collections.trie

import com.gitee.wsl.collections.iterator.api.MutableMapEntry
import com.gitee.wsl.collections.iterator.api.OrderedMapIterator
import com.gitee.wsl.collections.map.api.SequencedMap
import com.gitee.wsl.collections.map.api.SortedMap
import com.gitee.wsl.collections.trie.analyzer.KeyAnalyzer
import kotlin.concurrent.Volatile
import kotlin.jvm.Transient


/**
 * This class implements the base PATRICIA algorithm and everything that
 * is related to the [Map] interface.
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 4.0
</V></K> */
abstract class AbstractPatriciaTrie<K, V> : AbstractBitwiseTrie<K?, V?> {


    /**
     * A range view of the [org.apache.commons.collections4.Trie].
     */
    private abstract inner class AbstractRangeMap : AbstractMutableMap<K?,V?>(), SortedMap<K?,V?> {
        /** The [.entrySet] view.  */
        @Volatile
        @Transient
        private var entrySet: MutableSet<MutableMapEntry<K?,V?>>? = null

        override val comparator: Comparator<K?>
            get() = this@AbstractPatriciaTrie.comparator


        override fun reversed(): SequencedMap<K?, V?> {
            TODO("Not yet implemented")
        }

         override fun containsKey(key: K?): Boolean {
            if (!inRange(key)) {
                return false
            }

            return this@AbstractPatriciaTrie.containsKey(key)
        }

        /**
         * Creates and returns an [.entrySet] view of the [AbstractRangeMap].
         */
        protected abstract fun createEntrySet(): MutableSet<MutableMapEntry<K?,V?>>

        /**
         * Creates and returns a sub-range view of the current [AbstractRangeMap].
         */
        protected abstract fun createRangeMap(
            fromKey: K?, fromInclusive: Boolean,
            toKey: K?, toInclusive: Boolean,
        ): SortedMap<K?,V?>


        override val entries: MutableSet<MutableMapEntry<K?, V?>>
            get(){
                if (entrySet == null) {
                    entrySet = createEntrySet()
                }
                return entrySet!!
            }


         override fun get(key: K?): V? {
            if (!inRange(key)) {
                return null
            }

            return this@AbstractPatriciaTrie[key]
        }

        /**
         * Returns the FROM Key.
         */
         abstract val fromKey: K?

        /**
         * Returns the TO Key.
         */
         abstract val toKey: K?

        override fun headMap(toKey: K?): SortedMap<K?,V?> {
            require(inRange2(toKey)) { "ToKey is out of range: $toKey" }
            return createRangeMap(this.fromKey, this.isFromInclusive, toKey, this.isToInclusive)
        }

        /**
         * Returns true if the provided key is in the FROM range of the [AbstractRangeMap].
         */
        protected open fun inFromRange(key: K?, forceInclusive: Boolean): Boolean {
            val fromKey = this.fromKey
            val fromInclusive = this.isFromInclusive

            val ret = keyAnalyzer.compare(key, fromKey)
            if (fromInclusive || forceInclusive) {
                return ret >= 0
            }
            return ret > 0
        }

        /**
         * Returns true if the provided key is greater than TO and less than FROM.
         */
        open fun inRange(key: K?): Boolean {
            val fromKey = this.fromKey
            val toKey = this.toKey

            return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, false))
        }

        /**
         * This form allows the high endpoint (as well as all legit keys).
         */
        protected open fun inRange2(key: K?): Boolean {
            val fromKey = this.fromKey
            val toKey = this.toKey

            return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, true))
        }

        /**
         * Returns true if the provided key is in the TO range of the [AbstractRangeMap].
         */
        protected open fun inToRange(key: K?, forceInclusive: Boolean): Boolean {
            val toKey = this.toKey
            val toInclusive = this.isToInclusive

            val ret = keyAnalyzer.compare(key, toKey)
            if (toInclusive || forceInclusive) {
                return ret <= 0
            }
            return ret < 0
        }

        /**
         * Whether or not the [.getFromKey] is in the range.
         */
        protected abstract val isFromInclusive: Boolean

        /**
         * Whether or not the [.getToKey] is in the range.
         */
        protected abstract val isToInclusive: Boolean

         override fun put(key: K?, value: V?): V? {
            require(inRange(key)) { "Key is out of range: $key" }
            return this@AbstractPatriciaTrie.put(key, value)
        }

         override fun remove(key: K?): V? {
            if (!inRange(key)) {
                return null
            }

            return this@AbstractPatriciaTrie.remove(key)
        }

        override fun subMap(fromKey: K?, toKey: K?): SortedMap<K?,V?> {
            require(inRange2(fromKey)) { "FromKey is out of range: $fromKey" }

            require(inRange2(toKey)) { "ToKey is out of range: $toKey" }

            return createRangeMap(fromKey, this.isFromInclusive, toKey, this.isToInclusive)
        }

        override fun tailMap(fromKey: K?): SortedMap<K?,V?> {
            require(inRange2(fromKey)) { "FromKey is out of range: $fromKey" }
            return createRangeMap(fromKey, this.isFromInclusive, this.toKey, this.isToInclusive)
        }
    }

    /**
     * An iterator for the entries.
     */
    internal abstract inner class AbstractTrieIterator<E> : MutableIterator<E> {
        /** For fast-fail.  */
        protected var expectedModCount: Int = this@AbstractPatriciaTrie.modCount

        protected var next: TrieEntry<K,V>? // the next node to return
        protected var current: TrieEntry<K,V>? = null // the current entry we're on

        /**
         * Starts iteration from the root.
         */
        protected constructor() {
            next = this@AbstractPatriciaTrie.nextEntry(null)
        }

        /**
         * Starts iteration at the given entry.
         */
        protected constructor(firstEntry: TrieEntry<K,V>) {
            next = firstEntry
        }

        /**
         * @see PatriciaTrie.nextEntry
         */
        protected open fun findNext(prior: TrieEntry<K,V>): TrieEntry<K,V>? {
            return this@AbstractPatriciaTrie.nextEntry(prior)
        }

         override fun hasNext(): Boolean {
            return next != null
        }

        /**
         * Returns the next [TrieEntry].
         */
        protected open fun nextEntry(): TrieEntry<K,V> {
            if (expectedModCount != this@AbstractPatriciaTrie.modCount) {
                throw ConcurrentModificationException()
            }

            val e = next
            if (e == null) {
                throw NoSuchElementException()
            }

            next = findNext(e)
            current = e
            return e
        }

        override fun remove() {
            checkNotNull(current)

            if (expectedModCount != this@AbstractPatriciaTrie.modCount) {
                throw ConcurrentModificationException()
            }

            val node = current
            current = null
            this@AbstractPatriciaTrie.removeEntry(node!!)

            expectedModCount = this@AbstractPatriciaTrie.modCount
        }
    }

    /**
     * This is an entry set view of the [org.apache.commons.collections4.Trie] as returned by [Map.entrySet].
     */
    private inner class EntrySet : AbstractMutableSet<TrieEntry<K,V>>() {
        /**
         * An [Iterator] that returns [Entry] Objects.
         */
        private inner class EntryIterator() : AbstractTrieIterator<TrieEntry<K,V>>() {
             override fun next(): TrieEntry<K,V>{
                return nextEntry()
            }
        }

         override fun clear() {
            this@AbstractPatriciaTrie.clear()
        }

         override fun contains(element: TrieEntry<K,V>): Boolean {
//            if (o !is BasicEntry) {
//                return false
//            }

            val candidate = getEntry(element.key)
            return candidate != null && candidate == element
        }

         override fun iterator(): MutableIterator<TrieEntry<K,V>> {
            return EntryIterator()
        }

        override fun add(element: TrieEntry<K,V>): Boolean {
            TODO("Not yet implemented")
        }

         override fun remove(element: TrieEntry<K,V>): Boolean {
//            if (obj !is BasicEntry) {
//                return false
//            }
            if (!contains(element)) {
                return false
            }
            //val entry = element as BasicEntry<*, *>
            this@AbstractPatriciaTrie.remove(element.key)
            return true
        }

        override val size: Int
            get() = this@AbstractPatriciaTrie.size

    }

    /**
     * This is a key set view of the [org.apache.commons.collections4.Trie] as returned by [Map.keySet].
     */
    private inner class KeySet : AbstractMutableSet<K?>() {
        /**
         * An [Iterator] that returns Key Objects.
         */
        private inner class KeyIterator : AbstractTrieIterator<K>() {
             override fun next(): K {
                return nextEntry().key!!
            }
        }

         override fun clear() {
            this@AbstractPatriciaTrie.clear()
        }

         override fun contains(element: K?): Boolean {
            return containsKey(element)
        }

         override fun iterator(): MutableIterator<K> {
            return KeyIterator()
        }

        override fun add(element: K?): Boolean {
            TODO("Not yet implemented")
        }

         override fun remove(element: K?): Boolean {
            val localSize = size
            this@AbstractPatriciaTrie.remove(element)
            return localSize != size
        }

        override val size: Int
            get() = this@AbstractPatriciaTrie.size

    }

    /**
     * A prefix [RangeEntrySet] view of the [org.apache.commons.collections4.Trie].
     */
    private inner class PrefixRangeEntrySet(
        override val delegate: PrefixRangeMap
    ) : RangeEntrySet(delegate) {
        /**
         * An [Iterator] for iterating over a prefix search.
         */
        private inner class EntryIterator(
            // the subtree to search within
            private var subtree: TrieEntry<K,V>,
            prefix: K?,
            offset: Int,
            lengthInBits: Int,
        ) : AbstractTrieIterator<TrieEntry<K,V>>() {
            // values to reset the subtree if we remove it.
            private val prefix: K?
            private val offset: Int
            private val lengthInBits: Int
            private var lastOne = false

            /**
             * Starts iteration at the given entry &amp; search only
             * within the given subtree.
             */
            init {
                next = this@AbstractPatriciaTrie.followLeft(subtree)
                this.prefix = prefix
                this.offset = offset
                this.lengthInBits = lengthInBits
            }

            override fun findNext(prior: TrieEntry<K,V>): TrieEntry<K,V>? {
                return this@AbstractPatriciaTrie.nextEntryInSubtree(prior, subtree)
            }

             override fun next(): TrieEntry<K,V> {
                val entry = nextEntry()
                if (lastOne) {
                    next = null
                }
                return entry
            }

            override fun remove() {
                // If the current entry we're removing is the subtree
                // then we need to find a new subtree parent.
                var needsFixing = false
                val bitIdx = subtree.bitIndex
                if (current == subtree) {
                    needsFixing = true
                }

                super.remove()

                // If the subtree changed its bitIndex or we
                // removed the old subtree, get a new one.
                if (bitIdx != subtree.bitIndex || needsFixing) {
                    subtree = subtree(prefix, offset, lengthInBits)!!
                }

                // If the subtree's bitIndex is less than the
                // length of our prefix, it's the last item
                // in the prefix tree.
                if (lengthInBits >= subtree.bitIndex) {
                    lastOne = true
                }
            }
        }

        /**
         * An [Iterator] that holds a single [TrieEntry].
         */
        private inner class SingletonIterator(
               private val entry: TrieEntry<K,V>
          ) : MutableIterator<TrieEntry<K,V>> {
            private var hit = 0

             override fun hasNext(): Boolean {
                return hit == 0
            }

             override fun next(): TrieEntry<K,V> {
                if (hit != 0) {
                    throw NoSuchElementException()
                }

                ++hit
                return entry
            }

             override fun remove() {
                check(hit == 1)

                ++hit
                this@AbstractPatriciaTrie.removeEntry(entry)
            }
        }

        private var prefixStart: TrieEntry<K,V>? = null

        private var expectedModCount = 0

        override fun iterator(): MutableIterator<TrieEntry<K, V>> {
            if (this@AbstractPatriciaTrie.modCount != expectedModCount) {
                prefixStart = subtree(delegate.prefix, delegate.offsetInBits, delegate.lengthInBits)
                expectedModCount = this@AbstractPatriciaTrie.modCount
            }

            if (prefixStart == null) {
                val empty = mutableSetOf<TrieEntry<K,V>>()
                return empty.iterator()
            }
            if (delegate.lengthInBits > prefixStart!!.bitIndex) {
                return SingletonIterator(prefixStart!!)
            }
            return EntryIterator(
                prefixStart!!,
                delegate.prefix,
                delegate.offsetInBits,
                delegate.lengthInBits
            )
        }

        override val size: Int
            get() = delegate.fixup()

    }

    /**
     * A submap used for prefix views over the [org.apache.commons.collections4.Trie].
     */
    private inner class PrefixRangeMap(
        val prefix: K?,
        val offsetInBits: Int,
        val lengthInBits: Int
    ) : AbstractRangeMap() {
        override var fromKey: K? = null
            private set

        override var toKey: K? = null
            private set

        @Transient
        private var expectedModCount = 0

        override var size = -1

         override fun clear() {
            val it = this@AbstractPatriciaTrie.entries.iterator()
            val currentKeys = keys
            while (it.hasNext()) {
                if (currentKeys.contains(it.next().key)) {
                    it.remove()
                }
            }
        }

        override fun createEntrySet(): MutableSet<MutableMapEntry<K?, V?>> {
            return PrefixRangeEntrySet(this) as MutableSet<MutableMapEntry<K?, V?>>
        }

        override fun createRangeMap(
            fromKey: K?, fromInclusive: Boolean,
            toKey: K?, toInclusive: Boolean,
        ): SortedMap<K?,V?> {
            return RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive)
        }

        override fun firstKey(): K? {
            fixup()
            var e: MutableMapEntry<K?,V?>? = null
            if (fromKey == null) {
                e = firstEntry()
            } else {
                e = higherEntry(fromKey!!)
            }

            val first = e?.key
            if (e == null || !keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, first!!)) {
                throw NoSuchElementException()
            }

            return first
        }

        /**
         * This method does two things. It determines the FROM
         * and TO range of the [PrefixRangeMap] and the number
         * of elements in the range. This method must be called every
         * time the [org.apache.commons.collections4.Trie] has changed.
         */
        fun fixup(): Int {
            // The trie has changed since we last found our toKey / fromKey
            if (size == -1 || this@AbstractPatriciaTrie.modCount != expectedModCount) {
                val it = super.entries.iterator()
                size = 0

                var entry: MutableMapEntry<K?,V?>? = null
                if (it.hasNext()) {
                    entry = it.next()
                    size = 1
                }

                fromKey = entry?.key
                if (fromKey != null) {
                    val prior = previousEntry(entry as TrieEntry<K,V>)
                    fromKey = prior?.key
                }

                toKey = fromKey

                while (it.hasNext()) {
                    ++size
                    entry = it.next()
                }

                toKey = entry?.key

                if (toKey != null) {
                    entry = nextEntry(entry as TrieEntry<K,V>)
                    toKey = entry?.key
                }

                expectedModCount = this@AbstractPatriciaTrie.modCount
            }

            return size
        }

        /**
         * Returns true if the provided Key is in the FROM range of the [PrefixRangeMap].
         */
        override fun inFromRange(key: K?, forceInclusive: Boolean): Boolean {
            return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key)
        }

        /**
         * Returns true if this [PrefixRangeMap]'s key is a prefix of the provided key.
         */
        override fun inRange(key: K?): Boolean {
            return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key)
        }

        /**
         * Same as [.inRange].
         */
        override fun inRange2(key: K?): Boolean {
            return inRange(key)
        }

        /**
         * Returns true if the provided Key is in the TO range of the [PrefixRangeMap].
         */
        override fun inToRange(key: K?, forceInclusive: Boolean): Boolean {
            return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key)
        }

        override val isFromInclusive: Boolean
            get() = false

        override val isToInclusive: Boolean
            get() = false

        override fun lastKey(): K {
            fixup()

            var e: MutableMapEntry<K?,V?>? = null
            e = if (toKey == null) {
                lastEntry()
            } else {
                lowerEntry(toKey!!)
            }

            val last = e?.key
            if (e == null || !keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, last!!)) {
                throw NoSuchElementException()
            }

            return last
        }
    }

    /**
     * A [AbstractRangeMap] that deals with [Entry]s.
     */
    private inner class RangeEntryMap(
        override val fromKey: K?,
        override val isFromInclusive: Boolean,
        override val toKey: K?,
        override val isToInclusive: Boolean
    ) : AbstractRangeMap() {
        /** The key to start from, null if the beginning.  */
        //override val fromKey: K

        /** The key to end at, null if till the end.  */
        //override val toKey: K

        /** Whether or not the 'from' is inclusive.  */
        //override val isFromInclusive: Boolean

        /** Whether or not the 'to' is inclusive.  */
        //override val isToInclusive: Boolean

        /**
         * Creates a [RangeEntryMap].
         */
        init {
            require(!(fromKey == null && toKey == null)) { "must have a from or to!" }

            require(!(fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0)) { "fromKey > toKey" }

//            this.fromKey = fromKey
//            this.isFromInclusive = fromInclusive
//            this.toKey = toKey
//            this.isToInclusive = toInclusive
        }

        /**
         * Creates a [RangeEntryMap] with the fromKey included and
         * the toKey excluded from the range.
         */
        constructor(
            fromKey: K?,
            toKey: K?
        ) : this(fromKey, true, toKey, false)

        override fun createEntrySet(): MutableSet<MutableMapEntry<K?, V?>> {
            return RangeEntrySet(this) as MutableSet<MutableMapEntry<K?, V?>>
        }

        override fun createRangeMap(
            fromKey: K?, fromInclusive: Boolean,
            toKey: K?, toInclusive: Boolean,
        ): SortedMap<K?,V?> {
            return RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive)
        }

        override fun firstKey(): K? {
            var e: MutableMapEntry<K?,V?>? = null
            e = if (fromKey == null) {
                firstEntry()
            } else if (this.isFromInclusive) {
                ceilingEntry(fromKey)
            } else {
                higherEntry(fromKey)
            }

            val first = e?.key
            if (e == null || toKey != null && !inToRange(first!!, false)) {
                throw NoSuchElementException()
            }
            return first
        }

        override fun lastKey(): K? {
            val e = if (toKey == null) {
                lastEntry()
            } else if (this.isToInclusive) {
                floorEntry(toKey)
            } else {
                lowerEntry(toKey)
            }

            val last = e?.key
            if (e == null || fromKey != null && !inFromRange(last!!, false)) {
                throw NoSuchElementException()
            }
            return last
        }
    }

    /**
     * A [Set] view of a [AbstractRangeMap].
     */
    private open inner class RangeEntrySet(
        open val delegate: AbstractRangeMap
    ) : AbstractMutableSet<TrieEntry<K,V>>() {
        /**
         * An [Iterator] for [RangeEntrySet]s.
         */
        private inner class EntryIterator(
            first: TrieEntry<K,V>,
            last: TrieEntry<K,V>?
        ) : AbstractTrieIterator<TrieEntry<K,V>>(first) {
            private val excludedKey: K? = last?.key

            override fun hasNext(): Boolean {
                return next != null && !compare(next!!.key, excludedKey)
            }

             override fun next(): TrieEntry<K,V> {
                if (next == null || compare(next!!.key, excludedKey)) {
                    throw NoSuchElementException()
                }
                return nextEntry()
            }
        }

        //private val delegate: AbstractRangeMap = Objects.requireNonNull(delegate, "delegate")

        @Transient
        private var _size = -1

        @Transient
        private var expectedModCount = 0

         override fun contains(element: TrieEntry<K,V>): Boolean {
//            if (o !is MutableMapEntry) {
//                return false
//            }

            val entry = element
            val key = entry.key!!
            if (!delegate.inRange(key)) {
                return false
            }

            val node = getEntry(key)
            return node != null && compare(node.value, entry.value)
        }

         override fun isEmpty(): Boolean {
            return !iterator().hasNext()
        }

         override fun iterator(): MutableIterator<TrieEntry<K, V>> {
            val fromKey = delegate.fromKey
            val toKey = delegate.toKey
            val first: TrieEntry<K,V>? = if (fromKey == null) {
                firstEntry()
            } else {
                ceilingEntry(fromKey)
            }

            var last: TrieEntry<K,V>? = null
            if (toKey != null) {
                last = ceilingEntry(toKey)
            }

            return EntryIterator(first!!, last)
        }

        override fun add(element: TrieEntry<K, V>): Boolean {
            TODO("Not yet implemented")
        }

         override fun remove(element: TrieEntry<K,V>): Boolean {
//            if (o !is BasicEntry) {
//                return false
//            }

            val entry = element
            val key: K = entry.key!!
            if (!delegate.inRange(key)) {
                return false
            }

            val node = getEntry(key)
            if (node != null && compare(node.value, entry.value)) {
                removeEntry(node)
                return true
            }
            return false
        }

        override val size: Int
            get() {
                if (_size == -1 || expectedModCount != this@AbstractPatriciaTrie.modCount) {
                    _size = 0

                    val it: Iterator<*> = iterator()
                    while (it.hasNext()) {
                        ++_size
                        it.next()
                    }

                    expectedModCount = this@AbstractPatriciaTrie.modCount
                }
                return _size
            }

    }

    /**
     * A [Reference] allows us to return something through a Method's
     * argument list. An alternative would be to an Array with a length of
     * one (1) but that leads to compiler warnings. Computationally and memory
     * wise there's no difference (except for the need to load the
     * [Reference] Class but that happens only once).
     */
    private class Reference<E> {
        private var item: E? = null

        fun get(): E? {
            return item
        }

        fun set(item: E?) {
            this.item = item
        }
    }

    /**
     * A [org.apache.commons.collections4.Trie] is a set of [TrieEntry] nodes.
     *
     * @param <K> the key type.
     * @param <V> the value type.
    </V></K> */
    class TrieEntry<K, V>(
        key: K?,
        value: V?,
        /** The index this entry is comparing.  */
        var bitIndex: Int,
    ) : BasicEntry<K?,V?>(key, value) {
        /** The parent of this entry.  */
         var parent: TrieEntry<K,V>? = null

        /** The left child of this entry.  */
         var left: TrieEntry<K,V> = this

        /** The right child of this entry.  */
         var right: TrieEntry<K,V>? = null

        /** The entry who uplinks to this entry.  */
         var predecessor: TrieEntry<K,V> = this

        /**
         * Whether the entry is storing a key.
         * Only the root can potentially be empty, all other
         * nodes must have a key.
         *
         * @return Whether the entry is storing a key
         */
        val isEmpty: Boolean
            get() = key == null

        /**
         * Whether the left or right child is a loopback.
         *
         * @return Whether the left or right child is a loopback.
         */
        val isExternalNode: Boolean
            get() = !this.isInternalNode

        /**
         * Tests that neither the left nor right child is a loopback.
         *
         * @return That neither the left nor right child is a loopback.
         */
        val isInternalNode: Boolean
            get() = left !== this && right !== this

         override fun toString(): String {
            val buffer = StringBuilder()

            if (bitIndex == -1) {
                buffer.append("RootEntry(")
            } else {
                buffer.append("Entry(")
            }

            buffer.append("key=").append(key).append(" [").append(bitIndex).append("], ")
            buffer.append("value=").append(value).append(", ")

            //buffer.append("bitIndex=").append(bitIndex).append(", ");
            if (parent != null) {
                if (parent!!.bitIndex == -1) {
                    buffer.append("parent=").append("ROOT")
                } else {
                    buffer.append("parent=").append(parent!!.key).append(" [").append(parent!!.bitIndex).append("]")
                }
            } else {
                buffer.append("parent=").append("null")
            }
            buffer.append(", ")

            if (left != null) {
                if (left!!.bitIndex == -1) {
                    buffer.append("left=").append("ROOT")
                } else {
                    buffer.append("left=").append(left!!.key).append(" [").append(left!!.bitIndex).append("]")
                }
            } else {
                buffer.append("left=").append("null")
            }
            buffer.append(", ")

            if (right != null) {
                if (right!!.bitIndex == -1) {
                    buffer.append("right=").append("ROOT")
                } else {
                    buffer.append("right=").append(right!!.key).append(" [").append(right!!.bitIndex).append("]")
                }
            } else {
                buffer.append("right=").append("null")
            }
            buffer.append(", ")

            if (predecessor != null) {
                if (predecessor!!.bitIndex == -1) {
                    buffer.append("predecessor=").append("ROOT")
                } else {
                    buffer.append("predecessor=").append(predecessor!!.key).append(" [").append(predecessor!!.bitIndex).append("]")
                }
            }

            buffer.append(")")
            return buffer.toString()
        }

    }

    /**
     * An [OrderedMapIterator] for a [org.apache.commons.collections4.Trie].
     */
    private inner class TrieMapIterator : AbstractTrieIterator<K?>(), OrderedMapIterator<K?,V?> {
        protected var previous: TrieEntry<K,V>? = null // the previous node to return

        override fun getKey(): K? {
            checkNotNull(current)
            return current!!.key
        }

        override fun getValue(): V? {
            checkNotNull(current)
            return current!!.value
        }

        override fun hasPrevious(): Boolean {
            return previous != null
        }

        override fun next(): K? {
            return nextEntry().key
        }

        override fun nextEntry(): TrieEntry<K,V> {
            val nextEntry: TrieEntry<K,V> = super.nextEntry()
            previous = nextEntry
            return nextEntry
        }

        override fun previous(): K? {
            return previousEntry().key
        }

        protected fun previousEntry(): TrieEntry<K,V> {
            if (expectedModCount != this@AbstractPatriciaTrie.modCount) {
                throw ConcurrentModificationException()
            }

            val e = previous
            if (e == null) {
                throw NoSuchElementException()
            }

            previous = this@AbstractPatriciaTrie.previousEntry(e)
            next = current
            current = e
            return current!!
        }

        override fun setValue(value: V?): V? {
            checkNotNull(current)
            return current!!.setValue(value)
        }
    }

    /**
     * This is a value view of the [org.apache.commons.collections4.Trie] as returned by [Map.values].
     */
    private inner class Values : AbstractMutableCollection<V?>() {
        /**
         * An [Iterator] that returns Value Objects.
         */
        private inner class ValueIterator : AbstractTrieIterator<V?>() {
             override fun next(): V? {
                return nextEntry().value
            }
        }

         override fun clear() {
            this@AbstractPatriciaTrie.clear()
        }

         override fun contains(element: V?): Boolean {
            return containsValue(element)
        }

         override fun iterator(): MutableIterator<V?> {
            return ValueIterator()
        }

        override fun add(element: V?): Boolean {
            TODO("Not yet implemented")
        }

         override fun remove(element: V?): Boolean {
            val it = iterator()
            while (it.hasNext()) {
                val value = it.next()
                if (compare(value, element)) {
                    it.remove()
                    return true
                }
            }
            return false
        }

        override val size: Int
            get() = this@AbstractPatriciaTrie.size

    }

    /** The root node of the [org.apache.commons.collections4.Trie].  */
    @Transient
    private var root = TrieEntry<K,V>(null, null, -1)

    /**
     * Each of these fields are initialized to contain an instance of the
     * appropriate view the first time this view is requested. The views are
     * stateless, so there's no reason to create more than one of each.
     */
    @Volatile
    @Transient
    private var _keySet: MutableSet<K?>? = null

    @Volatile
    @Transient
    private var _values: MutableCollection<V?>? = null

    @Volatile
    @Transient
    private var _entrySet: MutableSet<MutableMap.MutableEntry<K?, V?>>? = null

    /** The current size of the [org.apache.commons.collections4.Trie].  */
    @Transient
    override var size = 0

    /**
     * The number of times this [org.apache.commons.collections4.Trie] has been modified.
     * It's used to detect concurrent modifications and fail-fast the [Iterator]s.
     */
    @Transient
    protected var modCount: Int = 0

    /**
     * Constructs a new [Trie] using the given [KeyAnalyzer].
     *
     * @param keyAnalyzer  the [KeyAnalyzer].
     */
    protected constructor(keyAnalyzer: KeyAnalyzer<K?>) : super(keyAnalyzer)

    /**
     * Constructs a new [org.apache.commons.collections4.Trie] using the given [KeyAnalyzer] and initializes the
     * [org.apache.commons.collections4.Trie] with the values from the provided [Map].
     *
     * @param keyAnalyzer  the [KeyAnalyzer].
     * @param map The source map.
     */
    protected constructor(keyAnalyzer: KeyAnalyzer<K?>, map: Map<K,V>) : super(keyAnalyzer) {
        putAll(map)
    }

    /**
     * Adds the given [TrieEntry] to the [org.apache.commons.collections4.Trie].
     */
    fun addEntry(entry: TrieEntry<K,V>, lengthInBits: Int): TrieEntry<K,V> {
        var current = root.left
        var path: TrieEntry<K,V> = root
        while (true) {
            if (current.bitIndex >= entry.bitIndex || current.bitIndex <= path.bitIndex) {
                entry.predecessor = entry

                if (!isBitSet(entry.key, entry.bitIndex, lengthInBits)) {
                    entry.left = entry
                    entry.right = current
                } else {
                    entry.left = current
                    entry.right = entry
                }

                entry.parent = path
                if (current.bitIndex >= entry.bitIndex) {
                    current.parent = entry
                }

                // if we inserted an uplink, set the predecessor on it
                if (current.bitIndex <= path.bitIndex) {
                    current.predecessor = entry
                }

                if (path === root || !isBitSet(entry.key, path.bitIndex, lengthInBits)) {
                    path.left = entry
                } else {
                    path.right = entry
                }

                return entry
            }

            path = current

            current = if (!isBitSet(entry.key, current.bitIndex, lengthInBits)) {
                current.left
            } else {
                current.right!!
            }
        }
    }

    /**
     * Returns a key-value mapping associated with the least key greater
     * than or equal to the given key, or null if there is no such key.
     */
    fun ceilingEntry(key: K): TrieEntry<K,V>? {
        // Basically:
        // Follow the steps of adding an entry, but instead...
        //
        // - If we ever encounter a situation where we found an equal
        //   key, we return it immediately.
        //
        // - If we hit an empty root, return the first iterable item.
        //
        // - If we have to add a new item, we temporarily add it,
        //   find the successor to it, then remove the added item.
        //
        // These steps ensure that the returned value is either the
        // entry for the key itself, or the first entry directly after
        // the key.

        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)

        val lengthInBits = lengthInBits(key)

        if (lengthInBits == 0) {
            if (!root.isEmpty) {
                return root
            }
            return firstEntry()
        }

        val found = getNearestEntryForKey(key, lengthInBits)
        if (compareKeys(key, found.key)) {
            return found
        }

        val bitIndex = bitIndex(key, found.key)
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            val added = TrieEntry<K,V>(key, null, bitIndex)
            addEntry(added, lengthInBits)
            incrementSize() // must increment because remove will decrement
            val ceil = nextEntry(added)
            removeEntry(added)
            modCount -= 2 // we didn't really modify it.
            return ceil
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            if (!root.isEmpty) {
                return root
            }
            return firstEntry()
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return found
        }

        // we should have exited above.
        throw IllegalStateException("invalid lookup: $key")
    }

     override fun clear() {
        root.key = null
        root.bitIndex = -1
        root.value = null

        root.parent = null
        root.left = root
        root.right = null
        root.predecessor = root

        size = 0
        incrementModCount()
    }

    override val comparator: Comparator<K?>
        get() = keyAnalyzer


     override fun containsKey(key: K?): Boolean {
        if (key == null) {
            return false
        }

        val key: K = key
        val lengthInBits = lengthInBits(key)
        val entry = getNearestEntryForKey(key, lengthInBits)
        return !entry.isEmpty && compareKeys(key, entry.key)
    }

    /**
     * A helper method to decrement the [org.apache.commons.collections4.Trie] size and increment the modification counter.
     */
    fun decrementSize() {
        size--
        incrementModCount()
    }


    override val entries: MutableSet<MutableMap.MutableEntry<K?, V?>>
        get() {
            if (_entrySet == null) {
                _entrySet = EntrySet() as MutableSet<MutableMap.MutableEntry<K?, V?>>
            }
            return _entrySet!!
        }

    /**
     * Returns the first entry the [org.apache.commons.collections4.Trie] is storing.
     *
     *
     * This is implemented by going always to the left until
     * we encounter a valid uplink. That uplink is the first key.
     */
     override fun firstEntry(): TrieEntry<K,V>? {
        // if Trie is empty, no first node.
        if (isEmpty()) {
            return null
        }
        return followLeft(root)
    }

    override fun firstKey(): K? {
        if (isEmpty()) {
            throw NoSuchElementException()
        }
        return firstEntry()?.key
    }

    /**
     * Returns a key-value mapping associated with the greatest key
     * less than or equal to the given key, or null if there is no such key.
     */
    fun floorEntry(key: K): TrieEntry<K,V>? {
        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)
        val lengthInBits = lengthInBits(key)

        if (lengthInBits == 0) {
            if (!root.isEmpty) {
                return root
            }
            return null
        }

        val found = getNearestEntryForKey(key, lengthInBits)
        if (compareKeys(key, found.key)) {
            return found
        }

        val bitIndex = bitIndex(key, found.key)
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            val added = TrieEntry<K,V>(key, null, bitIndex)
            addEntry(added, lengthInBits)
            incrementSize() // must increment because remove will decrement
            val floor = previousEntry(added)
            removeEntry(added)
            modCount -= 2 // we didn't really modify it.
            return floor
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            if (!root.isEmpty) {
                return root
            }
            return null
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return found
        }

        // we should have exited above.
        throw IllegalStateException("invalid lookup: $key")
    }

    /**
     * Goes left through the tree until it finds a valid node.
     */
    fun followLeft(node: TrieEntry<K,V>): TrieEntry<K,V> {
        var node = node
        while (true) {
            var child = node.left
            // if we hit root and it didn't have a node, go right instead.
            if (child.isEmpty) {
                child = node.right!!
            }

            if (child.bitIndex <= node.bitIndex) {
                return child
            }

            node = child
        }
    }

    /**
     * Traverses down the right path until it finds an uplink.
     */
    fun followRight(node: TrieEntry<K,V>?): TrieEntry<K,V>? {
        // if Trie is empty, no last entry.
        var node = node
        if (node?.right == null) {
            return null
        }

        // Go as far right as possible, until we encounter an uplink.
        while (node!!.right!!.bitIndex > node.bitIndex) {
            node = node.right
        }

        return node.right
    }

     override fun get(key: K?): V? {
        val entry = getEntry(key)
        return entry?.value
    }

    /**
     * Returns the entry associated with the specified key in the
     * PatriciaTrieBase.  Returns null if the map contains no mapping
     * for this key.
     *
     *
     * This may throw ClassCastException if the object is not of type K.
     */
    fun getEntry(key:K?): TrieEntry<K,V>? {
        if (key == null) {
            return null
        }

        val lengthInBits = lengthInBits(key)
        val entry = getNearestEntryForKey(key, lengthInBits)
        return if (!entry.isEmpty && compareKeys(key, entry.key)) entry else null
    }

    /**
     * Returns the nearest entry for a given key.  This is useful
     * for finding knowing if a given key exists (and finding the value
     * for it), or for inserting the key.
     *
     * The actual get implementation. This is very similar to
     * selectR but with the exception that it might return the
     * root Entry even if it's empty.
     */
    fun getNearestEntryForKey(key: K?, lengthInBits: Int): TrieEntry<K,V> {
        var current = root.left
        var path: TrieEntry<K,V> = root
        while (true) {
            if (current.bitIndex <= path.bitIndex) {
                return current
            }

            path = current
            current = if (!isBitSet(key, current.bitIndex, lengthInBits)) {
                current.left
            } else {
                current.right!!
            }
        }
    }

    /**
     * Returns a view of this [org.apache.commons.collections4.Trie] of all elements that are prefixed
     * by the number of bits in the given Key.
     *
     *
     * The view that this returns is optimized to have a very efficient
     * [Iterator]. The [SortedMap.firstKey],
     * [SortedMap.lastKey] &amp; [Map.size] methods must
     * iterate over all possible values in order to determine the results.
     * This information is cached until the PATRICIA [org.apache.commons.collections4.Trie] changes.
     * All other methods (except [Iterator]) must compare the given
     * key to the prefix to ensure that it is within the range of the view.
     * The [Iterator]'s remove method must also relocate the subtree
     * that contains the prefixes if the entry holding the subtree is
     * removed or changes. Changing the subtree takes O(K) time.
     *
     * @param key  the key to use in the search
     * @param offsetInBits  the prefix offset
     * @param lengthInBits  the number of significant prefix bits
     * @return a [SortedMap] view of this [org.apache.commons.collections4.Trie] with all elements whose
     * key is prefixed by the search key
     */
    private fun getPrefixMapByBits(key: K?, offsetInBits: Int, lengthInBits: Int): SortedMap<K?,V?> {
        val offsetLength = offsetInBits + lengthInBits
        require(offsetLength <= lengthInBits(key)) {
            (offsetInBits.toString() + " + " + lengthInBits + " > " + lengthInBits(key))
        }

        if (offsetLength == 0) {
            return this
        }

        return PrefixRangeMap(key, offsetInBits, lengthInBits)
    }

    override fun headMap(toKey: K?): SortedMap<K?,V?> {
        return RangeEntryMap(null, toKey)
    }

    /**
     * Returns an entry strictly higher than the given key,
     * or null if no such entry exists.
     */
    fun higherEntry(key: K): TrieEntry<K,V>? {
        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)
        val lengthInBits = lengthInBits(key)

        if (lengthInBits == 0) {
            if (!root.isEmpty) {
                // If data in root, and more after -- return it.
                if (size > 1) {
                    return nextEntry(root)
                }
                // If no more after, no higher entry.
                return null
            }
            // Root is empty & we want something after empty, return first.
            return firstEntry()
        }

        val found = getNearestEntryForKey(key, lengthInBits)
        if (compareKeys(key, found.key)) {
            return nextEntry(found)
        }

        val bitIndex = bitIndex(key, found.key)
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            val added = TrieEntry<K,V>(key, null, bitIndex)
            addEntry(added, lengthInBits)
            incrementSize() // must increment because remove will decrement
            val ceil = nextEntry(added)
            removeEntry(added)
            modCount -= 2 // we didn't really modify it.
            return ceil
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            if (!root.isEmpty) {
                return firstEntry()
            }
            if (size > 1) {
                return nextEntry(firstEntry())
            }
            return null
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return nextEntry(found)
        }

        // we should have exited above.
        throw IllegalStateException("invalid lookup: $key")
    }

    /**
     * A helper method to increment the modification counter.
     */
    private fun incrementModCount() {
        ++modCount
    }

    /**
     * A helper method to increment the [org.apache.commons.collections4.Trie] size and the modification counter.
     */
    fun incrementSize() {
        size++
        incrementModCount()
    }

    override val keys: MutableSet<K?>
        get() {
            if (_keySet == null) {
                _keySet = KeySet()
            }
            return _keySet!!
        }

    /**
     * Returns the last entry the [org.apache.commons.collections4.Trie] is storing.
     *
     *
     * This is implemented by going always to the right until
     * we encounter a valid uplink. That uplink is the last key.
     */
     override fun lastEntry(): TrieEntry<K,V>? {
        return followRight(root.left)
    }

    override fun lastKey(): K? {
        val entry = lastEntry()
        if (entry != null) {
            return entry.key
        }
        throw NoSuchElementException()
    }

    /**
     * Returns a key-value mapping associated with the greatest key
     * strictly less than the given key, or null if there is no such key.
     */
    fun lowerEntry(key: K): TrieEntry<K,V>? {
        // Basically:
        // Follow the steps of adding an entry, but instead...
        //
        // - If we ever encounter a situation where we found an equal
        //   key, we return it's previousEntry immediately.
        //
        // - If we hit root (empty or not), return null.
        //
        // - If we have to add a new item, we temporarily add it,
        //   find the previousEntry to it, then remove the added item.
        //
        // These steps ensure that the returned value is always just before
        // the key or null (if there was nothing before it).

        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)

        val lengthInBits = lengthInBits(key)

        if (lengthInBits == 0) {
            return null // there can never be anything before root.
        }

        val found = getNearestEntryForKey(key, lengthInBits)
        if (compareKeys(key, found.key)) {
            return previousEntry(found)
        }

        val bitIndex = bitIndex(key, found.key)
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            val added = TrieEntry<K,V>(key, null, bitIndex)
            addEntry(added, lengthInBits)
            incrementSize() // must increment because remove will decrement
            val prior = previousEntry(added)
            removeEntry(added)
            modCount -= 2 // we didn't really modify it.
            return prior
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            return null
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return previousEntry(found)
        }

        // we should have exited above.
        throw IllegalStateException("invalid lookup: $key")
    }

    override fun mapIterator(): OrderedMapIterator<K?,V?> {
        return TrieMapIterator()
    }

    /**
     * Returns the entry lexicographically after the given entry.
     * If the given entry is null, returns the first node.
     */
    fun nextEntry(node: TrieEntry<K,V>?): TrieEntry<K,V>? {
        if (node == null) {
            return firstEntry()
        }
        return nextEntryImpl(node.predecessor, node, null)
    }

    /**
     * Scans for the next node, starting at the specified point, and using 'previous'
     * as a hint that the last node we returned was 'previous' (so we know not to return
     * it again).  If 'tree' is non-null, this will limit the search to the given tree.
     *
     * The basic premise is that each iteration can follow the following steps:
     *
     * 1) Scan all the way to the left.
     * a) If we already started from this node last time, proceed to Step 2.
     * b) If a valid uplink is found, use it.
     * c) If the result is an empty node (root not set), break the scan.
     * d) If we already returned the left node, break the scan.
     *
     * 2) Check the right.
     * a) If we already returned the right node, proceed to Step 3.
     * b) If it is a valid uplink, use it.
     * c) Do Step 1 from the right node.
     *
     * 3) Back up through the parents until we encounter find a parent
     * that we're not the right child of.
     *
     * 4) If there's no right child of that parent, the iteration is finished.
     * Otherwise continue to Step 5.
     *
     * 5) Check to see if the right child is a valid uplink.
     * a) If we already returned that child, proceed to Step 6.
     * Otherwise, use it.
     *
     * 6) If the right child of the parent is the parent itself, we've
     * already found &amp; returned the end of the Trie, so exit.
     *
     * 7) Do Step 1 on the parent's right child.
     */
    fun nextEntryImpl(
        start: TrieEntry<K,V>,
        previous: TrieEntry<K,V>?,
        tree: TrieEntry<K,V>?,
    ): TrieEntry<K,V>? {
        var current = start

        // Only look at the left if this was a recursive or
        // the first check, otherwise we know we've already looked
        // at the left.
        if (previous == null || start != previous.predecessor) {
            while (!current.left.isEmpty) {
                // stop traversing if we've already
                // returned the left of this node.
                if (previous === current.left) {
                    break
                }

                if (Companion.isValidUplink(current.left, current)) {
                    return current.left
                }

                current = current.left
            }
        }

        // If there's no data at all, exit.
        if (current.isEmpty) {
            return null
        }

        // If we've already returned the left,
        // and the immediate right is null,
        // there's only one entry in the Trie
        // which is stored at the root.
        //
        //  / ("")   <-- root
        //  \_/  \
        //       null <-- 'current'
        //
        if (current.right == null) {
            return null
        }

        // If nothing valid on the left, try the right.
        if (previous != current.right) {
            // See if it immediately is valid.
            if (Companion.isValidUplink(current.right, current)) {
                return current.right
            }

            // Must search on the right's side if it wasn't initially valid.
            return nextEntryImpl(current.right!!, previous, tree)
        }

        // Neither left nor right are valid, find the first parent
        // whose child did not come from the right & traverse it.
        while (current === current.parent!!.right) {
            // If we're going to traverse to above the subtree, stop.
            if (current === tree) {
                return null
            }

            current = current.parent!!
        }

        // If we're on the top of the subtree, we can't go any higher.
        if (current === tree) {
            return null
        }

        // If there's no right, the parent must be root, so we're done.
        if (current.parent?.right == null) {
            return null
        }

        // If the parent's right points to itself, we've found one.
        if (previous !== current.parent?.right && isValidUplink(current.parent?.right, current.parent!!)
        ) {
            return current.parent?.right
        }

        // If the parent's right is itself, there can't be any more nodes.
        if (current.parent?.right === current.parent) {
            return null
        }

        // We need to traverse down the parent's right's path.
        return nextEntryImpl(current.parent!!.right!!, previous, tree)
    }

    /**
     * Returns the entry lexicographically after the given entry.
     * If the given entry is null, returns the first node.
     *
     * This will traverse only within the subtree.  If the given node
     * is not within the subtree, this will have undefined results.
     */
    fun nextEntryInSubtree(
        node: TrieEntry<K,V>?,
        parentOfSubtree: TrieEntry<K,V>?,
    ): TrieEntry<K,V>? {
        if (node == null) {
            return firstEntry()
        }
        return nextEntryImpl(node.predecessor, node, parentOfSubtree)
    }

    override fun nextKey(key: K?): K? {
        val entry = getEntry(key)
        if (entry != null) {
            val nextEntry = nextEntry(entry)
            return nextEntry?.key
        }
        return null
    }

    override fun prefixMap(key: K?): SortedMap<K?,V?> {
        return getPrefixMapByBits(key, 0, lengthInBits(key))
    }

    /**
     * Returns the node lexicographically before the given node (or null if none).
     *
     * This follows four simple branches:
     * - If the uplink that returned us was a right uplink:
     * - If predecessor's left is a valid uplink from predecessor, return it.
     * - Else, follow the right path from the predecessor's left.
     * - If the uplink that returned us was a left uplink:
     * - Loop back through parents until we encounter a node where
     * node != node.parent.left.
     * - If node.parent.left is uplink from node.parent:
     * - If node.parent.left is not root, return it.
     * - If it is root &amp; root isEmpty, return null.
     * - If it is root &amp; root !isEmpty, return root.
     * - If node.parent.left is not uplink from node.parent:
     * - Follow right path for first right child from node.parent.left
     *
     * @param start  the start entry
     */
    fun previousEntry(start: TrieEntry<K,V>): TrieEntry<K,V>? {
        val predecessor = start.predecessor
        requireNotNull(predecessor) { "must have come from somewhere!" }

        if (predecessor.right === start) {
            if (Companion.isValidUplink(predecessor.left, predecessor)) {
                return predecessor.left
            }
            return followRight(predecessor.left)
        }
        var node = predecessor
        while (node.parent != null && node == node.parent?.left) {
            node = node.parent!!
        }

        if (node.parent == null) { // can be null if we're looking up root.
            return null
        }

        if (Companion.isValidUplink(node.parent?.left, node.parent!!)) {
            if (node.parent?.left === root) {
                if (root.isEmpty) {
                    return null
                }
                return root
            }
            return node.parent?.left
        }
        return followRight(node.parent?.left)
    }

    override fun previousKey(key: K?): K? {
        val entry = getEntry(key)
        if (entry != null) {
            val prevEntry = previousEntry(entry)
            return prevEntry?.key
        }
        return null
    }

     override fun put(key: K?, value: V?): V? {

        val lengthInBits = lengthInBits(key)

        // The only place to store a key with a length
        // of zero bits is the root node
        if (lengthInBits == 0) {
            if (root.isEmpty) {
                incrementSize()
            } else {
                incrementModCount()
            }
            return root.setKeyValue(key, value)
        }

        val found = getNearestEntryForKey(key, lengthInBits)
        if (compareKeys(key, found.key)) {
            if (found.isEmpty) { // <- must be the root
                incrementSize()
            } else {
                incrementModCount()
            }
            return found.setKeyValue(key, value)
        }

        val bitIndex = bitIndex(key, found.key)
        if (!KeyAnalyzer.isOutOfBoundsIndex(bitIndex)) {
            if (KeyAnalyzer.isValidBitIndex(bitIndex)) { // in 99.999...9% the case
                /* NEW KEY+VALUE TUPLE */
                val t = TrieEntry<K,V>(key, value, bitIndex)
                addEntry(t, lengthInBits)
                incrementSize()
                return null
            }
            if (KeyAnalyzer.isNullBitKey(bitIndex)) {
                // A bits of the Key are zero. The only place to
                // store such a Key is the root Node!

                /* NULL BIT KEY */

                if (root.isEmpty) {
                    incrementSize()
                } else {
                    incrementModCount()
                }
                return root.setKeyValue(key, value)
            }
            if (KeyAnalyzer.isEqualBitKey(bitIndex) && found !== root) { // NOPMD
                incrementModCount()
                return found.setKeyValue(key, value)
            }
        }

        throw IllegalArgumentException("Failed to put: $key -> $value, $bitIndex")
    }

    /**
     * Deserializes an instance from an ObjectInputStream.
     *
     * @param in The source ObjectInputStream.
     * @throws IOException            Any of the usual Input/Output related exceptions.
     * @throws ClassNotFoundException A class of a serialized object cannot be found.
     */
//    @Throws(
//        IOException::class,
//        java.lang.ClassNotFoundException::class
//    )  // This will fail at runtime if the stream is incorrect
//    private fun readObject(`in`: ObjectInputStream) {
//        `in`.defaultReadObject()
//        root = TrieEntry<K,V>(null, null, -1)
//        val size: Int = `in`.readInt()
//        for (i in 0..<size) {
//            val k = `in`.readObject() as K
//            val v = `in`.readObject() as V?
//            put(k, v)
//        }
//    }

    /**
     * {@inheritDoc}
     *
     * @throws ClassCastException if provided key is of an incompatible type
     */
     override fun remove(key: K?): V? {
        if (key == null) {
            return null
        }

        val key: K = key
        val lengthInBits = lengthInBits(key)
        var current = root.left
        var path: TrieEntry<K,V> = root
        while (true) {
            if (current.bitIndex <= path.bitIndex) {
                if (!current.isEmpty && compareKeys(key, current.key)) {
                    return removeEntry(current)
                }
                return null
            }

            path = current

            current = if (!isBitSet(key, current.bitIndex, lengthInBits)) {
                current.left
            } else {
                current.right!!
            }
        }
    }

    /**
     * Removes a single entry from the [org.apache.commons.collections4.Trie].
     *
     * If we found a Key (Entry h) then figure out if it's
     * an internal (hard to remove) or external Entry (easy
     * to remove)
     */
    fun removeEntry(h: TrieEntry<K,V>): V? {
        if (h !== root) {
            if (h.isInternalNode) {
                removeInternalEntry(h)
            } else {
                removeExternalEntry(h)
            }
        }

        decrementSize()
        return h.setKeyValue(null, null)
    }

    /**
     * Removes an external entry from the [org.apache.commons.collections4.Trie].
     *
     * If it's an external Entry then just remove it.
     * This is very easy and straight forward.
     */
    private fun removeExternalEntry(h: TrieEntry<K,V>) {
        require(h !== root) { "Cannot delete root Entry!" }
        require(h.isExternalNode) { "$h is not an external Entry!" }

        val child: TrieEntry<K,V> = (if (h.left === h) h.right else h.left)!!

        val parent = h.parent!!

        if (parent.left === h) {
            parent.left = child
        } else {
            parent.right = child
        }

        // either the parent is changing, or the predecessor is changing.
        if (child.bitIndex > parent.bitIndex) {
            child.parent = parent
        } else {
            child.predecessor = parent
        }
    }

    /**
     * Removes an internal entry from the [org.apache.commons.collections4.Trie].
     *
     * If it's an internal Entry then "good luck" with understanding
     * this code. The Idea is essentially that Entry p takes Entry h's
     * place in the trie which requires some re-wiring.
     */
    private fun removeInternalEntry(h: TrieEntry<K,V>) {
        require(h !== root) { "Cannot delete root Entry!" }
        require(h.isInternalNode) { "$h is not an internal Entry!" }

        val p = h.predecessor

        // Set P's bitIndex
        p.bitIndex = h.bitIndex

        // Fix P's parent, predecessor and child Nodes
        run {
            val child: TrieEntry<K,V> = (if (p.left === h) p.right else p.left)!!

            // if it was looping to itself previously,
            // it will now be pointed from its parent
            // (if we aren't removing its parent --
            //  in that case, it remains looping to itself).
            // otherwise, it will continue to have the same
            // predecessor.
            if (p.predecessor === p && p.parent !== h) {
                p.predecessor = p.parent!!
            }

            val parent = p.parent!!

            if (parent.left === p) {
                parent.left = child
            } else {
                parent.right = child
            }
            if (child.bitIndex > parent.bitIndex) {
                child.parent = parent
            }
        }

        // Fix H's parent and child Nodes
        run {
            // If H is a parent of its left and right child
            // then change them to P
            if (h.left.parent === h) {
                h.left.parent = p
            }

            if (h.right?.parent === h) {
                h.right?.parent = p
            }

            // Change H's parent
            if (h.parent?.left === h) {
                h.parent?.left = p
            } else {
                h.parent?.right = p
            }
        }

        // Copy the remaining fields from H to P
        //p.bitIndex = h.bitIndex;
        p.parent = h.parent
        p.left = h.left
        p.right = h.right

        // Make sure that if h was pointing to any uplinks,
        // p now points to them.
        if (Companion.isValidUplink(p.left, p)) {
            p.left.predecessor = p
        }

        if (Companion.isValidUplink(p.right, p)) {
            p.right?.predecessor = p
        }
    }

    /**
     * Returns the [java.util.BasicEntry] whose key is closest in a bitwise XOR
     * metric to the given key. This is NOT lexicographic closeness.
     * For example, given the keys:
     *
     *
     *  1. D = 1000100
     *  1. H = 1001000
     *  1. L = 1001100
     *
     *
     * If the [org.apache.commons.collections4.Trie] contained 'H' and 'L', a lookup of 'D' would
     * return 'L', because the XOR distance between D &amp; L is smaller
     * than the XOR distance between D &amp; H.
     *
     * @param key  the key to use in the search
     * @return the [java.util.BasicEntry] whose key is closest in a bitwise XOR metric
     * to the provided key
     */
    fun select(key: K): TrieEntry<K,V>? {
        val lengthInBits = lengthInBits(key)
        val reference = Reference<TrieEntry<K,V>?>()
        if (!selectR(root.left, -1, key, lengthInBits, reference)) {
            return reference.get()
        }
        return null
    }

    /**
     * Returns the key that is closest in a bitwise XOR metric to the
     * provided key. This is NOT lexicographic closeness!
     *
     * For example, given the keys:
     *
     *
     *  1. D = 1000100
     *  1. H = 1001000
     *  1. L = 1001100
     *
     *
     * If the [org.apache.commons.collections4.Trie] contained 'H' and 'L', a lookup of 'D' would
     * return 'L', because the XOR distance between D &amp; L is smaller
     * than the XOR distance between D &amp; H.
     *
     * @param key  the key to use in the search
     * @return the key that is closest in a bitwise XOR metric to the provided key
     */
    fun selectKey(key: K): K? {
        val entry = select(key)
        if (entry == null) {
            return null
        }
        return entry.key
    }

    private fun selectR(
        h: TrieEntry<K,V>, bitIndex: Int,
        key: K, lengthInBits: Int,
        reference: Reference<TrieEntry<K,V>?>,
    ): Boolean {
        if (h.bitIndex <= bitIndex) {
            // If we hit the root Node and it is empty
            // we have to look for an alternative best
            // matching node.
            if (!h.isEmpty) {
                reference.set(h)
                return false
            }
            return true
        }

        if (!isBitSet(key, h.bitIndex, lengthInBits)) {
            if (selectR(h.left, h.bitIndex, key, lengthInBits, reference)) {
                return selectR(h.right!!, h.bitIndex, key, lengthInBits, reference)
            }
        } else if (selectR(h.right!!, h.bitIndex, key, lengthInBits, reference)) {
            return selectR(h.left, h.bitIndex, key, lengthInBits, reference)
        }
        return false
    }

    /**
     * Returns the value whose key is closest in a bitwise XOR metric to
     * the provided key. This is NOT lexicographic closeness!
     *
     * For example, given the keys:
     *
     *
     *  1. D = 1000100
     *  1. H = 1001000
     *  1. L = 1001100
     *
     *
     * If the [org.apache.commons.collections4.Trie] contained 'H' and 'L', a lookup of 'D' would
     * return 'L', because the XOR distance between D &amp; L is smaller
     * than the XOR distance between D &amp; H.
     *
     * @param key  the key to use in the search
     * @return the value whose key is closest in a bitwise XOR metric
     * to the provided key
     */
    fun selectValue(key: K): V? {
        val entry = select(key)
        if (entry == null) {
            return null
        }
        return entry.value
    }


//     override fun size(): Int {
//        return size
//    }

    override fun subMap(fromKey: K?, toKey: K?): SortedMap<K?,V?> {
        return RangeEntryMap(fromKey, toKey)
    }

    /**
     * Finds the subtree that contains the prefix.
     *
     * This is very similar to getR but with the difference that
     * we stop the lookup if h.bitIndex > lengthInBits.
     */
    fun subtree(prefix: K?, offsetInBits: Int, lengthInBits: Int): TrieEntry<K,V>? {
        var current = root.left
        var path: TrieEntry<K,V> = root
        while (true) {
            if (current.bitIndex <= path.bitIndex || lengthInBits <= current.bitIndex) {
                break
            }

            path = current
            current = if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
                current.left
            } else {
                current.right!!
            }
        }

        // Make sure the entry is valid for a subtree.
        val entry = if (current.isEmpty) path else current

        // If entry is root, it can't be empty.
        if (entry.isEmpty) {
            return null
        }

        val endIndexInBits = offsetInBits + lengthInBits

        // if root && length of root is less than length of lookup,
        // there's nothing.
        // (this prevents returning the whole subtree if root has an empty
        //  string and we want to lookup things with "\0")
        if (entry === root && lengthInBits(entry.key) < endIndexInBits) {
            return null
        }

        // Found key's length-th bit differs from our key
        // which means it cannot be the prefix...
        if (isBitSet(prefix, endIndexInBits - 1, endIndexInBits)
            != isBitSet(entry.key, lengthInBits - 1, lengthInBits(entry.key))
        ) {
            return null
        }

        // ... or there are less than 'length' equal bits
        val bitIndex = keyAnalyzer.bitIndex(
            prefix, offsetInBits, lengthInBits,
            entry.key, 0, lengthInBits(entry.key)
        )

        if (bitIndex >= 0 && bitIndex < lengthInBits) {
            return null
        }

        return entry
    }

    override fun tailMap(fromKey: K?): SortedMap<K?,V?> {
        return RangeEntryMap(fromKey, null)
    }


    override val values: MutableCollection<V?>
        get() {
            if (_values == null) {
                _values = Values()
            }
            return _values!!
        }

    /**
     * Serializes this object to an ObjectOutputStream.
     *
     * @param out the target ObjectOutputStream.
     * @throws IOException thrown when an I/O errors occur writing to the target stream.
     */
//    @Throws(IOException::class)
//    private fun writeObject(out: ObjectOutputStream) {
//        out.defaultWriteObject()
//        out.writeInt(this.size())
//        for (entry in entrySet()!!) {
//            out.writeObject(entry.getKey())
//            out.writeObject(entry.getValue())
//        }
//    }

    companion object {

        /**
         * Returns true if 'next' is a valid uplink coming from 'from'.
         */
        fun isValidUplink(next: TrieEntry<*, *>?, from: TrieEntry<*, *>): Boolean {
            return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty
        }
    }
}
